{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 5.2 Indicator random variables"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2-1\n",
    "\n",
    "> In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly one time? What is the probability that you hire exactly $n$ times?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* Extractly one time\n",
    "\n",
    "The best candidate comes first, which is $\\frac{1}{n}$.\n",
    "\n",
    "* Extractly $n$ times\n",
    "\n",
    "The candidates presented in ascending order, which is $\\frac{1}{n!}$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2-2\n",
    "\n",
    "> In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what is the probability that you hire exactly twice?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose the first candidate is of rank $k$, followed by some candidates with rank less than $k$, then followed the candidate with rank $n$.\n",
    "\n",
    "$$\n",
    "P=\\sum_{k=1}^{n-1}\\frac{1}{n}\\frac{1}{n-k}=\\frac{1}{n}\\sum_{i=1}^{n-1}\\frac{1}{i}=O \\left ( \\frac{\\lg n}{n} \\right )\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2-3\n",
    "\n",
    "> Use indicator random variables to compute the expected value of the sum of $n$ dice."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$\n",
    "E[X_i] = \\frac{1+2+3+4+5+6}{6} = 3.5\n",
    "$$\n",
    "\n",
    "$$\n",
    "\\begin{array}{rll}\n",
    "E[X] &=& \\displaystyle E \\left [ \\sum_{i=1}^n X_i \\right ] \\\\\n",
    "&=& \\displaystyle \\sum_{i=1}^n E[X_i] \\\\\n",
    "&=& \\displaystyle \\sum_{i=1}^n 3.5 \\\\\n",
    "&=& \\displaystyle 3.5n\n",
    "\\end{array}\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2-4\n",
    "\n",
    "> Use indicator random variables to solve the following problem, which is known as the __*hat-check problem*__. Each of $n$ customers gives a hat to a hat-check person at a restaurant. The hat-check person gives the hats back to the customers in a random order. What is the expected number of customers who get back their own hat?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The probability of one customer get his/her hat back is $1/n$, therefore the expectation is $n \\dot (1/n) = 1$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 5.2-5\n",
    "\n",
    "> Let $A[1 \\dots n]$ be an array of $n$ distinct numbers. If $i < j$ and $A[i] > A[j]$, then the pair $(i,j)$ is called an __*inversion*__ of $A$. (See Problem 2-4 for more on inversions.) Suppose that the elements of $A$ form a uniform random permutation of $\\left \\langle 1, 2, \\dots, n \\right \\rangle$. Use indicator random variables to compute the expected number of\n",
    "inversions."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose $X_{ij} = I\\{(i, j) \\text{ is an inversion}\\}$,\n",
    "\n",
    "$$\n",
    "E[X_{ij}] = \\frac{1}{2}\n",
    "$$\n",
    "\n",
    "$$\n",
    "E[X] = \\sum_{i=1}^{n-1} \\sum_{j=i+1}^{n} E[X_{ij}]\n",
    "= \\frac{n(n-1)}{4}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
